# -*- coding: utf8 -*-
"""
Hopf algebra : Planar Binary Tree.

AUTHOR:

- Jean-Baptiste Priez
"""
#*****************************************************************************
#       Copyright (C) 2012 Jean-Baptiste Priez <jbp@kerios.fr>,
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#    This code is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#    General Public License for more details.
#
#  The full text of the GPL is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************
from good_hopf_algebra import GoodHopfAlgebras
from pattern import FundamentalBasis, FundamentalDualBasis, \
    getitem_for_wordlike_indices
from sage.categories.graded_hopf_algebras_with_basis import \
    GradedHopfAlgebrasWithBasis
from sage.categories.realizations import Category_realization_of_parent
from sage.combinat.free_module import CombinatorialFreeModule
from sage.misc.bindable_class import BindableClass
from sage.structure.parent import Parent
from sage.structure.unique_representation import UniqueRepresentation
from sage.combinat.permutation import Permutation

def getitem_tree( self, c, *rest ):
    from sage.rings.integer import Integer
    from sage.combinat.permutation import Permutations
    from sage.combinat.binary_tree import LabelledBinaryTrees, BinaryTrees
    from sage.sets.set import Set
    if isinstance( c, ( int, Integer ) ):
        assert( c == 1 ), "it must be like a permutation or a tree"
        res = self.indices()( Permutation( [] ) )
    elif len( c ) > 1 and all( [isinstance( i, ( int, Integer ) ) for i in c] ):
        s = Set( c )
        assert( min( s ) == 1 and max( s ) == s.cardinality() ), "it must be like a permutation or a tree"
        res = self.indices()( self.phi( Permutation(list( c ) + list( rest ) ) ) )
    elif len( c ) == 0 and len ( rest ) == 0:
        res = self.phi( Permutation( [] ) )
    else:
        res = {
            BinaryTrees() : lambda x: x,
            LabelledBinaryTrees() : lambda x: x.shape(),
            Permutations() : lambda x: self.phi( x )
        }[parent( c )]( c )
    return self.monomial( res )

def latex_term( self, m ):
    from sage.misc.latex import latex
    if len( m ) == 0 :
        return self.print_options()['latex_prefix'] + "_{\\cdot}"
    return self.print_options()['latex_prefix'] + "_{\\vcenter{\\hbox{\\scalebox{.3}\n{" + latex( m ) + "}}}}"

def repr_term( self, c ):
    """
    The default implementation gives double brackets
    """
    s = canonical_permutation( c )
    return self.prefix() + str( s ).replace( " ", "" )

def canonical_permutation( bt ):
    ''' Make the canonical standard word of bt
    EXAMPLES::
        
        sage: from sage.combinat.binary_tree import BinaryTree
        sage: B = BinaryTree
        sage: b = B([B([]),B([])]);b # the shape tree 312
        [[., .], [., .]]
        sage: _postfixe_reading(b)
        [3, 1, 2]
    '''
    def pr( bt, i = [1] ):
        if not bt[0].is_empty(): pr( bt[0] )
        j = i[0]
        i[0] += 1
        if not bt[1].is_empty(): pr( bt[1] )
        res.append( j )
    res = []
    if not  bt.is_empty() :
        pr( bt )
    return Permutation( res )

def sylvester_class( bt ):
    ''' Compute all permutations 'sigma' in the sylvester class
    associate to 'bt'.

    EXAMPLES::

        sage: B = BinaryTree
        sage: b = B([B([]),B([])]);b # the shape tree 312
        [[., .], [., .]]
        sage: _classe(b)
        [[3, 1, 2],[1, 3, 2]]
    '''
    from sage.combinat.binary_tree import LabelledBinaryTree
    def __classeSylv( forest, w = [] ):
        '''
            Compute all permutations which forms the shape
            of bt by insertion in binary search tree.
        '''
        if len( forest ) == 0 :
            return [w]
        res = []
        for t in forest :
            tmp = list( forest )
            tmp.remove( t )
            for ti in t :
                if not ti.is_empty():
                    tmp += [ti]
            res += __classeSylv( tmp, [int( t.label() )] + w )
        return res
    # compute the canonical permutation : sigma
    w = canonical_permutation( bt )
    if len( w ) == 0 : return [w]
    # compute the labelled binary search tree of sigma
    bt = LabelledBinaryTree( None )
    for l in w.reverse() : bt = bt.binary_search_insert( l )
    return [Permutation( w ) for w in __classeSylv( [bt] )]

class PlanarBinaryTreeFunctions( UniqueRepresentation, Parent ):
    '''

    '''
    def __init__( self, R ):
        '''
        EXAMPLES::

            sage: PBT = PlanarBinaryTreeFunctions(ZZ);PBT
            Hopf algebra of Planar Binary Trees Functions over the Integer Ring
        '''
        from sage.categories.all import Rings
        assert( R in Rings() )
        self._base = R
        Parent.__init__( self, category = GoodHopfAlgebras( R ).WithRealizations() )

    def phi( self, permutation ):
        '''
        EXAMPLES::
        
            sage: PBT(QQ).phi(Permutation([1,3,2]))
              o
             / \
            o   o
        
        TESTS::
        
            sage: PBT(QQ).phi(Permutation([1,3,2]))
            [[., .], [., .]]
        '''
        return permutation.binary_search_tree( False ).shape()

    def indices( self ):
        '''
        TESTS::

            sage: PBT(QQ).indices()
            Binary trees
        '''
        from sage.combinat.binary_tree import BinaryTrees
        return BinaryTrees()

    def _repr_( self ):
        return "Hopf algebra of Planar Binary Trees Functions over the %s" % self.base_ring()

    def a_realization( self ):
        return self.P()

    def dual( self ):
        return self

    def __init_extra__( self ):
        '''
        TESTS::

            sage: from all import FQSym, PBT
            sage: pbt = PBT(QQ); fqs = FQSym(QQ)
            sage: P = pbt.P(); Q = pbt.Q(); F = fqs.F(); G = fqs.G()
            sage: F(P[3,1,2]) ## P --> F
            F[1, 3, 2] + F[3, 1, 2]
            sage: F(P[3,1,2] * P[1]) == F(P[3,1,2]) * F(P[1])
            True
            sage: F(P[3,1,2] * P[3,4,2,1]) == F(P[3,1,2]) * F(P[3,4,2,1])
            True
            sage: G(Q[3,1,2]) ## G <--> Q
            G[1, 3, 2]
            sage: Q(G[1,3,2] * G[2,1,4,3]) == Q[3,1,2] * Q[2,4,1,3]
            True
            sage: Q(G[6,4,5,1,2,3] * G[5,1,3,2,4]) == Q(G[1,4,2,6,5,3] * G[3,1,5,2,4])
            True
            sage: Q(G[3,1,2]) ==  P(F[2,3,1]) # P <--> Q
            True
            sage: Q(G(F(P[1,2,4,3]))) == Q(P[1,2,4,3])
            True
        '''
        morph = lambda F, T, func, tri = None: F._module_morphism( 
            func, codomain = T, triangular = tri )

        P = self.P(); Q = self.Q(); E = self.E(); H = self.H()
        # P <-> Q
        P_to_Q = morph( P, Q, lambda x: Q( G( F( P( x ) ) ) ) )
        P_to_Q.register_as_coercion()
        Q_to_P = morph( Q, P, lambda x: P( F( G( Q( x ) ) ) ) )
        Q_to_P.register_as_coercion()

        # H <-> P
        H_to_P = morph( H, P, P.all_pred_tree, tri = "lower" )
        H_to_P.register_as_coercion()
        ( ~H_to_P ).register_as_coercion()

        # E <-> P
        E_to_P = morph( E, P, P.all_succ_tree, tri = "upper" )
        E_to_P.register_as_coercion()
        ( ~E_to_P ).register_as_coercion()

        ### Coercion and conversion with FQSym ###
        from all import FQSym
        FQS = FQSym( self.base() )
        F = FQS.F(); G = FQS.G()
        # F <-> P
        P_to_F = morph( P, F, lambda t : F.sum_of_monomials( P.tree_to_permutations( t ) ) )
        P_to_F.register_as_coercion()

        # G <-> Q
        G_to_Q = morph( G, Q, lambda x: Q.monomial( Q.phi( x ) ) )
        G_to_Q.register_as_conversion()

    _shorthands = set( ['P', 'Q', 'H', 'E'] )

    class Bases( Category_realization_of_parent ):

        def super_categories( self ):
            R = self.base().base_ring()
            return [self.base().Realizations(),
                    GoodHopfAlgebras( R ).Realizations(),
                    GradedHopfAlgebrasWithBasis( R ).Realizations()]

        class ParentMethods:

            def one_basis( self ):
                return self.indices()()

            def tree_to_permutations( self, tree ):
                return sylvester_class( tree )

            def all_succ_tree( self, tree ):
                return self.sum_of_monomials( tree.sylvestrohedron_greater() )

            def all_pred_tree( self, tree ):
                return self.sum_of_monomials( tree.sylvestrohedron_smaller() )


    class Fundamental( BindableClass, CombinatorialFreeModule ):

        def __init__( self, PBT ):
            CombinatorialFreeModule.__init__( 
                self, PBT.base_ring(), PBT.indices(),
                category = PBT.Bases(),
                prefix = "P", latex_prefix = "\\mathbb{P}",
                bracket = False )

        _latex_term = latex_term
        _repr_term = repr_term
        __getitem__ = getitem_tree

        def product_on_basis( self, bt1, bt2 ):
            r"""
            The product of the P basis : shuffle of tree

            EXAMPLES::
                P    * P    = P      + P    + P      + P      + P    + P
                 o        o    o        o        o        o        o        o
                  \      /      \        \        \      /        /        /
                   o    o        o        o        o    o        o        o
                                  \      /        /      \        \      /
                                   o    o        o        o        o    o
                                  /      \      /          \      /      \
                                 o        o    o            o    o        o

                P        * P      = P            + P              + P              +
                   _o_        o        _o_            __o___           ___o___      
                  /   \      / \      /   \          /      \         /       \     
                 o     o    o   o    o     o        o       _o_      o         o    
                  \                   \     \        \     /   \      \       / \   
                   o                   o     o        o   o     o      o     o   o  
                                            / \            \                /       
                                           o   o            o              o        
                                                                                    
                                                                                    
                 P              + P              + P
                       __o___            __o__             o_
                      /      \          /     \           /  \
                    _o_       o      __o__     o         o    o
                   /   \            /     \             /
                  o     o          o       o          _o_
                   \     \          \     /          /   \
                    o     o          o   o          o     o
                                                     \
                                                      o

            TESTS::
            
                sage: P[[]]**2
                P[]
                sage: P[1]**2
                P[2, 1] + P[1, 2]
                sage: P[1]*P[1,2]
                P[2, 3, 1] + P[2, 1, 3] + P[1, 2, 3]
                sage: P[2,1]*P[1,2]
                P[3, 4, 2, 1] + P[3, 2, 4, 1] + P[2, 3, 4, 1] + P[3, 2, 1, 4] + P[2, 3, 1, 4] + P[2, 1, 3, 4]
                sage: P[1,2]*P[2,1]
                P[1, 4, 3, 2] + P[1, 2, 4, 3]   
                sage: P[1,3,2]*P[1,2]
                P[1, 4, 5, 3, 2] + P[1, 4, 3, 5, 2] + P[1, 3, 4, 5, 2] + P[1, 4, 3, 2, 5] + P[1, 3, 4, 2, 5] + P[1, 3, 2, 4, 5] 
            """
            from tree_shuffle_product import TreeShuffleProduct
            return self.sum_of_monomials( bt for bt in TreeShuffleProduct( bt1, bt2 ) )

        def coproduct_on_basis( self, bt ):
            r"""
            The coproduct of the P basis : deconcatenation of tree
            
            EXAMPLES::
            
            delta /P   \ = 1 # P    + P  # P  + P    # 1
                  |   o|          o    o    o      o
                  |  / |         /                /
                  \ o  /        o                o

            delta /P     \ = 1 # P      + P  # P    + P  # P    + P    # P  + P    # P  +
                  |   o  |          o      o    o      o      o    o      o      o    o  
                  |  / \ |         / \           \           /      \           /        
                  \ o   o/        o   o           o         o        o         o         
             P      # 1
                o
               / \
              o   o
              
            TESTS::

                sage: P = PBT(QQ).P()
                sage: P[[]].coproduct()
                P[] # P[]
                sage: P[1].coproduct()
                P[] # P[1] + P[1] # P[]
                sage: P[1,3,2].coproduct()
                P[] # P[1,3,2] + P[1] # P[2,1] + P[1] # P[1,2] + P[2,1] # P[1] + P[1,2] # P[1] + P[1,3,2] # P[]

            EXAMPLES::

                sage: P = PBT(QQ).P()
                sage: P[4,2,1,3].coproduct()
                P[] # P[2, 1, 4, 3] + P[1] # P[1, 3, 2] + P[1] # P[2, 1, 3] + P[2, 1] # P[2, 1] + P[2, 1] # P[1, 2] + P[3, 2, 1] # P[1] + P[2, 3, 1] # P[1] + P[1, 2] # P[1, 2] + P[2, 1, 3] # P[1] + P[2, 1, 4, 3] # P[]
            """
            from sage.categories.tensor import tensor
            def extract_sub_tree_from_root( bt ):
                B = self.indices()
                if bt.is_empty():
                    yield ( [], bt )
                    return
                yield ( [bt], B() )
                for ( l0, b0 ) in extract_sub_tree_from_root( bt[0] ):
                    for ( l1, b1 ) in extract_sub_tree_from_root( bt[1] ):
                        yield ( l0 + l1, B( [b0, b1] ) )
            return self.tensor_square().sum( 
                map( lambda ( li, bt ): tensor( 
                            [self.prod( map( self.monomial, li ) ), self.monomial( bt ) ] ),
                    extract_sub_tree_from_root( bt ) ) )

    P = Fundamental

    class FundamentalDual( BindableClass, CombinatorialFreeModule ):

        def __init__( self, PBT ):
            CombinatorialFreeModule.__init__( 
                self, PBT.base_ring(), PBT.indices(),
                category = PBT.Bases(),
                prefix = "Q", latex_prefix = "\\mathbb{Q}",
                bracket = False )

        def product_on_basis( self, c1, c2 ):
            r'''
            The product of the Q-basis : concatenation of tree

            EXAMPLES::
            
                Q    * Q    = Q        + Q        + Q      + Q        + Q      + Q
                 o        o      o          _o_        o          o          o        o
                  \      /      / \        /   \      /          / \        /        /
                   o    o      o   o      o     o    o          o   o      o        o
                                    \      \          \        /          / \      /
                                     o      o          o      o          o   o    o
                                                        \                          \
                                                         o                          o

            TESTS::
            
                sage: Q = PBT(QQ).Q()
                sage: Q[2,1]**2
                Q[4, 3, 2, 1] + Q[2, 4, 3, 1] + Q[3, 2, 4, 1] + Q[1, 4, 3, 2] + Q[1, 3, 4, 2] + Q[2, 1, 4, 3]
                sage: Q[1,3,2] * Q[1,2]
                Q[1, 3, 5, 4, 2] + Q[2, 1, 5, 4, 3] + Q[2, 3, 1, 5, 4] + Q[2, 4, 3, 1, 5] + Q[1, 2, 5, 4, 3] + Q[1, 3, 2, 5, 4] + Q[1, 4, 3, 2, 5] + Q[1, 2, 3, 5, 4] + Q[1, 2, 4, 3, 5] + Q[1, 3, 2, 4, 5]
            '''
            from sage.combinat.words.word import Word
            from sage.sets.set import Set
            c1 = Word( canonical_permutation( c1 ).inverse() )
            c2 = Word( canonical_permutation( c2 ).inverse() )
            ens = c1.shifted_shuffle( c2 )
            return self.sum_of_monomials( [self.phi( Permutation( s ).inverse() ) for s in ens] )

        def coproduct_on_basis( self, p ):
            r"""
            The coproduct of the Q basis : de-shuffle of tree
            
            EXAMPLES::
            
                delta /Q   \ = 1 # Q    + Q  # Q  + Q    # 1
                      |   o|          o    o    o      o
                      |  / |         /                /
                      \ o  /        o                o

            delta /Q     \ = 1 # Q      + Q  # Q    + Q    # Q  + Q      # 1
                  |   o  |          o      o    o        o    o      o
                  |  / \ |         / \           \      /           / \
                  \ o   o/        o   o           o    o           o   o
            TESTS::
            
                sage: Q = PBT(QQ).Q()
                sage: Q[[]].coproduct()
                Q[] # Q[]
                sage: Q[1].coproduct()
                Q[] # Q[1] + Q[1] # Q[]
                sage: Q[1,2].coproduct()
                Q[] # Q[1,2] + Q[1] # Q[1] + Q[1,2] # Q[]
                sage: Q[1,2,3].coproduct()
                Q[] # Q[1,2,3] + Q[1] # Q[1,2] + Q[1,2] # Q[1] + Q[1,2,3] # Q[]
                sage: Q[1,3,2].coproduct()
                Q[] # Q[1,3,2] + Q[1] # Q[2,1] + Q[1,2] # Q[1] + Q[1,3,2] # Q[]
            """
            def restrict( bt ):
                if bt.is_empty():
                    yield ( bt, bt )
                    return
                for bm, bM in restrict( bt[1] ):
                    yield ( self.indices()( [bt[0], bm] ), bM )
                for bm, bM in restrict( bt[0] ):
                    yield ( bm, self.indices()( [bM, bt[1]] ) )
            return self.tensor_square().sum_of_monomials( restrict( p ) )

        _latex_term = latex_term
        _repr_term = repr_term
        __getitem__ = getitem_tree

    Q = FundamentalDual

    class Complete( BindableClass, CombinatorialFreeModule ):
        r'''
        TESTS::
        '''
        def __init__( self, PBT ):
            CombinatorialFreeModule.__init__( 
                self, PBT.base_ring(), PBT.indices(),
                category = PBT.Bases(),
                prefix = "H", latex_prefix = "\\mathcal{H}",
                bracket = False )

        _latex_term = latex_term
        _repr_term = repr_term
        __getitem__ = getitem_tree

        def product_on_basis( self, t1, t2 ):
            r"""
            The product of the H-basis
            
            EXAMPLES::
            
                H      * H          = H
                   o        __o__        _o_
                  / \      /     \      /   \
                 o   o    o       o    o     o
                           \     /            \
                            o   o            __o__
                                            /     \
                                           o       o
                                            \     /
                                             o   o

            TESTS::

                sage: H = PBT(QQ).Complete()
                sage: H[3,1,2] * H[4,5,2,1,3]
                H[1, 5, 4, 7, 8, 6, 3, 2]
            """
            def insert_at_the_bottom_right( t1, t2 ):
                if t1.is_empty() :
                    return t2
                return self.indices()( [t1[0], insert_at_the_bottom_right( t1[1], t2 )] )

            return self.monomial( insert_at_the_bottom_right( t1, t2 ) )

    H = Complete

    class Elementary( BindableClass, CombinatorialFreeModule ):
        r'''
        TESTS::
        '''
        def __init__( self, PBT ):
            CombinatorialFreeModule.__init__( 
                self, PBT.base_ring(), PBT.indices(),
                category = PBT.Bases(),
                prefix = "E", latex_prefix = "\\mathcal{E}",
                bracket = False )

        _latex_term = latex_term
        _repr_term = repr_term
        __getitem__ = getitem_tree

        def product_on_basis( self, t1, t2 ):
            r"""
            The product of the E-basis
            
            EXAMPLES::
            
                E      * E          = E
                   o        __o__             __o___
                  / \      /     \           /      \
                 o   o    o       o        _o_       o
                           \     /        /   \     /
                            o   o        o     o   o
                                        / \
                                       o   o

            TESTS::

                sage: E = PBT(QQ).Elementary()
                sage: E[3,1,2] * E[4,5,2,1,3]
                E[1, 3, 2, 5, 4, 7, 8, 6]
                sage: E[4,3,5,1,2] * E[4,3,1,2]
                E[1, 4, 3, 5, 2, 6, 9, 8, 7]
            """
            def insert_at_the_bottom_left( t1, t2 ):
                if t2.is_empty() :
                    return t1
                return self.indices()( [insert_at_the_bottom_left( t1, t2[0] ), t2[1]] )
            return self.monomial( insert_at_the_bottom_left( t1, t2 ) )

    E = Elementary


